package main

type Node struct {
	Key int
	Val  int
	Prev *Node
	Next *Node
}

type LRUCache struct {
	capacity int
	m        map[int]*Node
	head     *Node // 最近访问的放最后面
	end      *Node
}

func Constructor(capacity int) LRUCache {
	end := &Node{}
	head := &Node{Next: end}
	end.Prev = head
	return LRUCache{
		capacity: capacity,
		m:        make(map[int]*Node),
		head:     head,
		end:      end,
	}
}

func (this *LRUCache) rm(n *Node) {
	n.Prev.Next = n.Next
	if n.Next != nil {
		n.Next.Prev = n.Prev
	}
}

func (this *LRUCache) pop() {
	n := this.head.Next
	if n != this.end {
		this.rm(n)
		delete(this.m, n.Key)
	}
}

func (this *LRUCache) append(n *Node) {
	n.Prev = this.end.Prev
	n.Next = this.end
	this.end.Prev.Next = n
	this.end.Prev = n
}

func (this *LRUCache) Get(key int) int {
	n := this.m[key]
	if n == nil {
		return -1
	}
	this.rm(n)
	this.append(n)
	return n.Val
}

func (this *LRUCache) Put(key int, value int) {
	n := this.m[key]
	if n != nil {
		// 已经存在，更新一下顺序
		n.Val = value
		this.rm(n)
		this.append(n)
		return
	}
	if len(this.m) >= this.capacity {
		this.pop()
	}
	n = &Node{Key: key, Val: value}
	this.append(n)
	this.m[key] = n
}

func main() {
	c := Constructor(2)
	c.Put(1, 1)
	c.Put(2, 2)
	println(c.Get(1))
	c.Put(3, 3)
	println(c.Get(2))
}
